#include <iostream>
#include <stdlib.h>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;
// Defines
#define bigint unsigned long long int
#define dicc map<char,int>
#define filaMatriz vector< bigint >
#define matriz vector< vector< bigint > >
#define esta(x,m) m.count(x) == 1


// Completa la matriz de datos con la informacion de las reglas.
void completarMatriz(matriz &datos, dicc &alfabeto, vector<string> reglas, int tamTemp){
    int tamRegla;
    string regla;
    set<char> claves;
    for (int i = 0 ; i < tamTemp; i++ ){
		claves.insert(reglas[i][0]);
    }
    
    for (int i = 0 ; i < tamTemp; i++ ){
        tamRegla = reglas[i].size();
        regla = reglas[i];
        for(int j = 3 ; j < tamRegla; j++ ){
            datos[alfabeto[regla[0]]][alfabeto[regla[j]]]++;
			if(!esta(regla[j],claves)){
                if(!(datos[alfabeto[regla[j]]][alfabeto[regla[j]]] > 0)){
					datos[alfabeto[regla[j]]][alfabeto[regla[j]]]++;
				}
            }
        }    
    }
}

// Multiplica un vector x una Matriz y guarda la multiplicacion en el vector.
void vectorXMatriz(filaMatriz &v, matriz &m){
    
    int tam = v.size();
    vector<bigint> temporal = v;
    bigint suma;
    
	temporal = v;
	for(int j = 0 ; j < tam; j++ ){
		suma = 0;
		for(int k = 0 ; k < tam; k++){
			suma += temporal[k] * m[k][j];
		}
		v[j] = suma;
	}
}

// Multiplica un vector K veces por una matriz.
void multiplicarKveces(filaMatriz &V, matriz &datos, int K){
	for (int i = 0; i < K; ++i) vectorXMatriz(V, datos);
}

// Arma el vector asociado al string inicial.
void vectorInicial(dicc &alfabeto,string &inicial, filaMatriz &vectorInicial){
	int tam = inicial.size();
    for(int i = 0; i < tam; i++){
        if ( esta(inicial[i], alfabeto) ){
            vectorInicial[alfabeto[inicial[i]]]++;
        }
    }
}

// Cuenta la cantidad de apariciones de un caracter en un string.
bigint contarApariciones(char caracter, string &palabra){  
    int tam = palabra.size();
    bigint res = 0;
    for (int i = 0; i < tam; ++i) {
        if (palabra[i] == caracter) res++;
    }
    return res;
}

int main() {   
    string regla; 	// Captura reglas
    string inicial; // Captura el string inicial de la query
    char caracter; 	// Captura que el caracter cuyas apariciones debo contar 
    int potencia;	// Captura la potencia.
    int casos; 		// Captura la cantidad de reglas
    int reglas; 	// Captura la cantidad de casos
    int querys; 	// Captura la cantidad de querys
    int elem; 		// Contador de la cantidad de elementos que se van a considerar
    int reglai;  
    
    scanf("%d", &casos);
          
    for (int c = 0; c < casos; ++c) {
		bigint res = 0; // Almacena resultado
        dicc alfabeto; // Almacena el alfabeto utilizado
        elem = 0;
        
        scanf("%d", &reglas);
        reglai = reglas;
        vector<string> temporal(reglas, "");
        while(reglas > 0){
            pair<map<char,int>::iterator,bool> ret;
            cin >> regla;
            temporal[reglai - reglas] = regla;
            for(unsigned int i = 0; i < regla.size(); i++){ 
                if (regla[i] != '-' && regla[i] != '>'){
                    ret = alfabeto.insert(pair<char, int>(regla[i], elem));
                    // si ya está insertado el elemento
                    if(ret.second==true) elem++;
                }
            }
            reglas--;
        }
        
        matriz datos(alfabeto.size(), filaMatriz(alfabeto.size(), 0));   
        
        completarMatriz(datos, alfabeto, temporal, reglai);
            
        scanf("%d", &querys);
        
        for (int q = 0; q < querys; ++q) {
            cin >> inicial >> caracter >> potencia;
            
            if(!esta(caracter,alfabeto)){      
                res = contarApariciones(caracter, inicial);
            } else{
                filaMatriz init(alfabeto.size(),0);
                vectorInicial(alfabeto,inicial, init);   
                multiplicarKveces(init, datos,  potencia);
                res = init[alfabeto[caracter]]; 
            }

            printf("%llu\n", res);    
        }     
    } 
    return 0;
}
